29/09/2017

\[ \]

Dynamic Queueing Networks: Simulation, Estimation and Prediction

What's a queue?

What's a queue?

Arrival time: \(a_j\), when customer \(j\) arrives

Service time: \(s_j\), how much time customer \(j\) needs with a server

Departure time: \(d_j\), when customer \(j\) has been served

Waiting time: \(w_j = d_j - a_j - s_j\), how long customer \(j\) waited to be served

Kendall's notation

\(f_{\delta} / f_s / K / C / n / R\)

\(f_{\delta}\): inter-arrival distribution

\(f_s\): service distribution

\(K\): number of servers

\(C\): capacity of system

\(n\): number of customers

\(R\): service discipline

Performance measures

system utilization: \(\rho = \frac{\mu}{\lambda}\)

The steady state probability of \(N\) customers in a \(M/M/K\) system is,

\[ \begin{align} P(0) &= \left[\frac{ (K \rho)^K}{K! (1 - \rho)} + 1 + \sum_{i=1}^{K-1} \frac{(K \rho)^i}{i!} \right]^{-1} \\ P(N) &= \begin{cases} P(0) \frac{(K \rho)^n }{N!} & \quad N \leq K\\ P(0) \frac{(K \rho)^n }{K! K^{N-K}} & \text{otherwise} \end{cases} , \label{eq:pn} \end{align} \]

Simulation

R package queuecomputer

It's fast

Computation time in milliseconds for varying numbers of passengers for each DES/queueing package.

Queueing Networks

Sutton, C., & Jordan, M. I. (2011). Bayesian inference for queueing networks and modeling of internet services. The Annals of Applied Statistics, 254-282.

International Airport

Queueing network model of an international airport terminal.

International Airport Data

Approach

Simulation is used to convert \(\mathbf{(a,s)}\) to departure times \(\mathbf{d}\). \(\mathbf{Z}\) in step 7 is a function of the \(\mathbf{(a,s)}, \mathbf{d}\) and \(\theta_C\). It reflects features such as average waiting time, average queue length and resource utilization.

Simulation

Simulation

library(AirportSimulator)
suppressPackageStartupMessages(library(dplyr))

airport_simulate() %>% sample_frac()
## # A tibble: 15,602 x 49
##    FlightNo Passengers arrival chocks  gate       Aus Flight_lag distance
##       <chr>      <dbl>   <dbl>  <dbl> <dbl>     <dbl>      <dbl>    <dbl>
##  1   STU374        204  844.81 849.81     7 0.5493974         10       50
##  2   MMV426        202  475.15 480.15    11 0.1687726         12      100
##  3   GFG548        188  437.41 442.41     8 0.7446436          9       50
##  4   RDL588        207  509.19 514.19     8 0.3548210          7       50
##  5   MGK352        205  873.68 878.68     4 0.2227345         10       25
##  6   AJQ982        203  843.63 848.63     6 0.2964728         11       50
##  7   QIH619        199  986.85 991.85    10 0.8941724         13      100
##  8   MMV426        202  475.15 480.15    11 0.1687726         12      100
##  9   OLY647        189  596.11 601.11     3 0.3986504          8       25
## 10   HOC337        230  950.22 955.22     5 0.5917895         15       25
## # ... with 15,592 more rows, and 41 more variables: walk_imm <dbl>,
## #   walk_aerobridge <dbl>, walk_bh <dbl>, walk_quarantine <dbl>,
## #   passenger_num <int>, service_aerobridge <dbl>, nationality <fctr>,
## #   walk_AC <dbl>, route_prob <dbl>, route_imm <fctr>, service_rate <dbl>,
## #   num_baggage <dbl>, route_prob_1_quarantine <dbl>,
## #   route_prob_2_quarantine <dbl>, route_baggage <dbl>, service_imm <dbl>,
## #   n_bags <int>, route_quarantine <chr>, rate_quarantine <dbl>,
## #   service_quarantine <dbl>, service_bags <dbl>, server_imm <list>,
## #   server_baggage <list>, server_quarantine <list>, arrive_AC <dbl>,
## #   arrive_imm <dbl>, depart_imm <dbl>, arrival_bags <dbl>,
## #   depart_bags <dbl>, arrive_bh <dbl>, depart_bh <dbl>,
## #   arrive_quarantine <dbl>, depart_quarantine <dbl>,
## #   route_imm_true <fctr>, dwell_AC <dbl>, wait_imm <dbl>,
## #   dwell_imm <dbl>, wait_bh <dbl>, dwell_bh <dbl>, wait_q <dbl>,
## #   dwell_q <dbl>

Estimation: Approximate Bayesian Computation

For many complex models \(f (y|\theta)\) is easy to sample from but difficult or impossible to evaluate. Intuitively we may think that the best way to estimate \(\theta\), based on observed data \(y\), is to take samples from \(f (y|\theta)\) with different values of \(\theta\) until \(x\) “looks like” \(y\).

Estimation: Maximum Mean Discrepancy

\[ \begin{align} \widehat{\text{MMD}}^2_b(X,Y|s) &= \frac{1}{m^2} \sum_{i,j = 1}^{m} k(x_i, x_j) \\ &\quad + \frac{1}{n^2} \sum_{i,j = 1}^{n} k(y_i, y_j) - \frac{2}{mn} \sum_{i,j = 1}^{m,n} k(x_i, y_j). \end{align} \]

Gretton, A., Borgwardt, K. M., Rasch, M., Schölkopf, B., & Smola, A. J. (2007). A kernel method for the two-sample-problem. In Advances in neural information processing systems (pp. 513-520).

Estimation

library(AirportSimulator)

true_params <- c(0.2, 20, 1.1, 3.5, 0.8, 3)

y <- airport_sim_1(true_params)

x <- airport_sim_1(true_params)

airport_MMD(y,x, threshold = 6)
## [1] 0.0243735
proposed_params <- c(0.2, 10, 0.5, 3.5, 0.8, 3)

x <- airport_sim_1(proposed_params)

airport_MMD(y,x, threshold = 6)
## [1] 0.04856347

Estimation

library(tidyr)
library(ggplot2)
data_frame(y = unlist(y), x = unlist(x), input_output = rep(c("input", "output"), each = 15602)) %>% 
  gather(key = "key", value = "time", y, x) %>%
  ggplot(aes(x = time, col = input_output)) +  
  geom_density(adjust = 0.0001) +
  facet_grid(key ~ .)

Estimation: Results

ABC posterior distributions.

Prediction

Distribution of average waiting time for passengers by flight. Resimulations with fixed parameters.

Prediction

Particle resampling of trajectories with data assimilation.

Thank you!


Anthony Ebert
Supervised by: Kerrie Mengersen, Paul Wu, Fabrizio Ruggeri

Email: ac.ebert@qut.edu.au
Github: AnthonyEbert
Twitter: @ace_ebert

Have a look at the R package queuecomputer

This work is supported by the Australian Research Council Centre of Excellence for Mathematical and Statistical Frontiers (ACEMS).